翻訳と辞書 Words near each other ・ Lineodes dianalis ・ Lineodes elcodes ・ Lineodes encystalis ・ Lineodes fontella ・ Lineodes formosalis ・ Lineodes furcillata ・ Linear predictive analysis ・ Linear predictive coding ・ Linear predictor function ・ Linear probability model ・ Linear probing ・ Linear production game ・ Linear programming ・ Linear programming decoding ・ Linear programming formulation ・ Linear programming relaxation ・ Linear progression ・ Linear range ・ Linear Recording ・ Linear referencing ・ Linear regression ・ Linear regression (disambiguation) ・ Linear regulator ・ Linear response function ・ Linear scale ・ Linear scheduling method ・ Linear script ・ Linear search ・ Linear search problem ・ Linear seismic inversion Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Linear programming relaxation ： ウィキペディア英語版 Linear programming relaxation In mathematics, the linear programming relaxation of a 0-1 integer program is the problem that arises by replacing the constraint that each variable must be 0 or 1 by a weaker constraint, that each variable belong to the interval (). That is, for each constraint of the form :$x\_i\backslash in\backslash$ of the original integer program, one instead uses a pair of linear constraints :$0\; \backslash le\; x\_i\; \backslash le\; 1.$ The resulting relaxation is a linear program, hence the name. This relaxation technique transforms an NP-hard optimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming); the solution to the relaxed linear program can be used to gain information about the solution to the original integer program. ==Example== Consider the set cover problem, the linear programming relaxation of which was first considered by . In this problem, one is given as input a family of sets ''F'' = ; the task is to find a subfamily, with as few sets as possible, having the same union as ''F''. To formulate this as a 0-1 integer program, form an indicator variable ''xi'' for each set ''Si'', that takes the value 1 when ''Si'' belongs to the chosen subfamily and 0 when it does not. Then a valid cover can be described by an assignment of values to the indicator variables satisfying the constraints :$\backslash textstyle\; x\_i\backslash in\backslash$ (that is, only the specified indicator variable values are allowed) and, for each element ''ej'' of the union of ''F'', :$\backslash textstyle\; \backslash sum\_\{\backslash \{i\backslash mid\; e\_j\backslash in\; S\_i\backslash \}\}\; x\_i\; \backslash ge\; 1$ (that is, each element is covered). The minimum set cover corresponds to the assignment of indicator variables satisfying these constraints and minimizing the linear objective function :$\backslash textstyle\; \backslash min\; \backslash sum\_i\; x\_i.$ The linear programming relaxation of the set cover problem describes a ''fractional cover'' in which the input sets are assigned weights such that the total weight of the sets containing each element is at least one and the total weight of all sets is minimized. As a specific example of the set cover problem, consider the instance ''F'' = . There are three optimal set covers, each of which includes two of the three given sets. Thus, the optimal value of the objective function of the corresponding 0-1 integer program is 2, the number of sets in the optimal covers. However, there is a fractional solution in which each set is assigned the weight 1/2, and for which the total value of the objective function is 3/2. Thus, in this example, the linear programming relaxation has a value differing from that of the unrelaxed 0-1 integer program. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Linear programming relaxation」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.